1. Field of the Invention
This invention is related to a method and system for identifying path-delay faults in integrated circuits in which a path status graph is created to represent the status of each simulated path-delay fault of the circuit.
2. Description of the Related Art
Increasing performance of integrated circuits can be achieved through operating the circuit at the highest possible speed. Operation of integrated circuits at high speeds increases the probability of failures of the chips fabricated with the circuit due to timing deviations. The timing deviations can be the result of manufacturing tolerances, design errors or incorrect statistical modeling of the timing behavior.
A logic circuit may be expected to operate correctly during successive "clock" periods. A "delay-fault" occurs when a circuit response requires more time than specified by design requirements. The delay of a digital circuit is the maximum time needed for outputs of the circuit to be determined after inputs to the circuit have changed. Signal transitions can travel through paths from primary inputs, gates or flip-flop outputs to primary outputs or flip-flop inputs of the circuit. For example, a path-delay fault (PDF) models when the cumulative delay of propagating a transition along a path of the circuit exceeds a predetermined limit. The predetermined limit can be a clock period. Delay-fault testing can be used to check if the circuit meets the required clock rate or speed requirements by detecting PDFs in the circuit.
An approach for modeling path-delay faults uses two path-delay faults for each path based on the direction of the transition, as described in G. L. Smith, Model For Delay Faults Based upon Paths, In Proc. ITC, pages 342-349, November 1985. The two path-delay faults are defined as rising and falling PDFs. This model directly represents the timing intent of the circuit.
Conventionally, delay-fault testing is performed with path-delay fault simulators. The path-delay fault simulators provide fault detection of a circuit with respect to a given test set. The simulators can be integrated into automatic test-pattern generation tools for providing the test set. Typically, the path-delay fault simulators store the status of the targeted faults in a data structure. During the course of simulation, the status is "true" if the fault is tested by the patterns simulated thus far, otherwise the status is "false".
Conventional approaches use one location to store the status of each fault at the beginning of the simulation, see: S. Bose, P. Agrawal and V. D. Agrawal, Path Delay Fault Simulation of Sequential Circuits, IEEE Trans. on VLSI Systems, 1(4):453:461, December, 1993; I. Pomeranz, L. N. Reddy and S. M. Reddy, SPADES: A Simulator For Path Delay Faults in Sequential Circuits, In Proc. Euro-DAC, pages 428-435, September 1992, and G. L. Smith, Model For Delay Faults Based Upon Paths, In Proc. ITC, pages 342-349, November 1985. Alternatively, an approach described in B. Kapoor, An Efficient Method For Computing Exact Path Delay Fault Coverage, In Proc. European Design and Test Conference, pages 516-520, March 1995 uses a tree data structure in which memory locations are dynamically allocated for tested faults during the course of simulation. In this approach, implicit enumeration of paths is represented as the tested paths which are consecutively numbered using one leaf node. If the tested paths do not have consecutive numbers, the number of leaf nodes is also proportional to the number of tested paths. In another approach, described in M. H. Schulz, F. Fink and K. Fuchs, Parallel Pattern Fault Simulation of Path Delay Faults, In Proc. 26th DAC, pages 357-363, June 1989, the number of leaf nodes is proportional to the number of tested paths. Since the number of paths in a circuit can be very large, the number of targeted faults may also be large. The above-described approaches have the drawback that with finite storage space and computational effort, it is likely that the above approaches will be impractical for circuits with large numbers of paths.
A non-enumerative data structure that grows polynomially with the circuit size is described in I. Pomeranz and S. M. Reddy, An Efficient Non-Enumerative Method To Estimate Path Delay Fault Coverage, In Proc. ICCAD, pages 560-567, November 1992. This approach provides an estimate of the fault coverage in which the accuracy improves as the degree of the polynomial is increased. This method has the limitation that it is exact only when the degree of the polynomial is proportional to the circuit size, resulting in exponential complexity.
It is desirable to provide a method and system for efficiently simulating path delay faults.